{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Subarrays in a Valid Split"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validSubarraySplit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有效分割中的最少子数组数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>nums</code>。</p>\n",
    "\n",
    "<p>如果要将整数数组 <code>nums</code> 拆分为&nbsp;<strong>子数组&nbsp;</strong>后是&nbsp;<strong>有效的</strong>，则必须满足:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个子数组的第一个和最后一个元素的最大公约数&nbsp;<strong>大于</strong> <code>1</code>，且</li>\n",
    "\t<li><code>nums</code> 的每个元素只属于一个子数组。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <code>nums</code>&nbsp;的&nbsp;<strong>有效&nbsp;</strong>子数组拆分中的&nbsp;<strong>最少&nbsp;</strong>子数组数目。如果不能进行有效的子数组拆分，则返回 <code>-1</code>。</p>\n",
    "\n",
    "<p><b>注意</b>:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>两个数的&nbsp;<strong>最大公约数&nbsp;</strong>是能整除两个数的最大正整数。</li>\n",
    "\t<li><strong>子数组&nbsp;</strong>是数组中连续的非空部分。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [2,6,3,4,3]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 我们可以通过以下方式创建一个有效的分割: [2,6] | [3,4,3].\n",
    "- 第一个子数组的起始元素是 2，结束元素是 6。它们的最大公约数是 2，大于 1。\n",
    "- 第二个子数组的起始元素是 3，结束元素是 3。它们的最大公约数是 3，大于 1。\n",
    "可以证明，2 是我们在有效分割中可以获得的最少子数组数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [3,5]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 我们可以通过以下方式创建一个有效的分割: [3] | [5].\n",
    "- 第一个子数组的起始元素是 3，结束元素是 3。它们的最大公约数是 3，大于 1。\n",
    "- 第二个子数组的起始元素是 5，结束元素是 5。它们的最大公约数是 5，大于 1。\n",
    "可以证明，2 是我们在有效分割中可以获得的最少子数组数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,1]\n",
    "<strong>输出:</strong> -1\n",
    "<strong>解释:</strong> 不可能创建有效的分割。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-subarrays-in-a-valid-split](https://leetcode.cn/problems/minimum-subarrays-in-a-valid-split/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-subarrays-in-a-valid-split](https://leetcode.cn/problems/minimum-subarrays-in-a-valid-split/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,6,3,4,3]', '[3,5]', '[1,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySplit(self, nums: List[int]) -> int:\n",
    "        dp = [10**9 for j in range(len(nums))]\n",
    "        for j in range(len(nums)):\n",
    "            for i in range(j+1):\n",
    "                if math.gcd(nums[i],nums[j])>1:\n",
    "                    dp[j]=min(dp[j],dp[i-1]+1) if i else 1\n",
    "        return dp[-1] if dp[-1]<10**9 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySplit(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[float('inf')]*(n+1)\n",
    "        dp[0]=0\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                if gcd(nums[i],nums[j])>1:\n",
    "                    dp[j+1]=min(dp[j+1],dp[i]+1)\n",
    "        if dp[-1]==float('inf'):return -1\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # dp\n",
    "from math import gcd\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySplit(self, nums: List[int]) -> int:\n",
    "        if nums[0] == 1 or nums[-1] == 1:\n",
    "            return -1\n",
    "\n",
    "        d = {-1: 0}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1:\n",
    "                continue\n",
    "\n",
    "            min_length = 2000\n",
    "            for j in range(i + 1):\n",
    "                if j - 1 in d and gcd(nums[j], nums[i]) > 1:\n",
    "                    min_length = min(min_length, d[j - 1] + 1)\n",
    "\n",
    "            if min_length < 2000:\n",
    "                d[i] = min_length\n",
    "\n",
    "        return d.get(len(nums) - 1, -1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySplit(self, nums: List[int]) -> int:\n",
    "\n",
    "        dp = [10**9 for j in range(len(nums))]\n",
    "        for j in range(len(nums)):\n",
    "            for i in range(j+1):\n",
    "                if math.gcd(nums[i],nums[j])>1:\n",
    "                    dp[j]=min(dp[j],dp[i-1]+1) if i else 1\n",
    "        return dp[-1] if dp[-1]<10**9 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySplit(self, nums: List[int]) -> int:\n",
    "        # 初始化dp数组，初始值设置为一个大数\n",
    "        dp = [10**9 for j in range(len(nums))]\n",
    "        \n",
    "        for j in range(len(nums)):\n",
    "            for i in range(j+1):\n",
    "                # 检查最大公约数是否大于1\n",
    "                if math.gcd(nums[i], nums[j]) > 1:\n",
    "                    # 更新dp值\n",
    "                    dp[j] = min(dp[j], dp[i-1] + 1) if i else 1\n",
    "        \n",
    "        # 检查最后一个dp值是否被更新，如果没更新则返回-1\n",
    "        return dp[-1] if dp[-1] < 10**9 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def validSubarraySplit(self, nums: List[int]) -> int:\r\n",
    "        if nums[0] == 1 or nums[-1] == 1:\r\n",
    "            return -1\r\n",
    "        d = {-1: 0}\r\n",
    "        for i in range(len(nums)):\r\n",
    "            if nums[i] == 1:\r\n",
    "                continue\r\n",
    "            min_length = 2000\r\n",
    "            for j in range(i + 1):\r\n",
    "                if j - 1 in d and gcd(nums[j], nums[i]) > 1:\r\n",
    "                    min_length = min(min_length, d[j - 1] + 1)\r\n",
    "            if min_length < 2000:\r\n",
    "                d[i] = min_length\r\n",
    "        return d.get(len(nums) - 1, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if nums[0] == 1 or nums[-1] == 1:\n",
    "            return -1\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        # f = [[1] * n for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i, n):\n",
    "        #         f[i][j] = gcd(nums[i], nums[j])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = inf \n",
    "            flag = False\n",
    "            for j in range(i, n):\n",
    "                if gcd(nums[i], nums[j]) > 1:\n",
    "                    flag = True \n",
    "                    res = min(res, 1 + dfs(j + 1))\n",
    "            if not flag:\n",
    "                return inf\n",
    "            return res \n",
    "        \n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySplit(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i == n: return 0\n",
    "            rnt = inf\n",
    "            for j in range(i, n):\n",
    "                if gcd(nums[i], nums[j]) > 1:\n",
    "                    rnt = min(rnt, 1 + f(j+1))\n",
    "\n",
    "            return rnt\n",
    "        ans = -1 if f(0) == inf else f(0)\n",
    "        f.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def min_factor(n):\r\n",
    "    sieve = list(range(n + 1))\r\n",
    "    sieve[2::2] = [2] * (n // 2)\r\n",
    "    for i in range(3, int(n ** 0.5) + 2, 2):\r\n",
    "        if sieve[i] == i:\r\n",
    "            sieve[i * i::2 * i] = [i] * ((n - i * i) // (2 * i) + 1)\r\n",
    "    return sieve\r\n",
    "\r\n",
    "\r\n",
    "N = 100010\r\n",
    "table = min_factor(N)\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def validSubarraySplit(self, nums: List[int]) -> int:\r\n",
    "        f = {}\r\n",
    "        pre = 0\r\n",
    "        for num in nums:\r\n",
    "            cur = N\r\n",
    "            while num != 1:\r\n",
    "                f[table[num]] = min(f.get(table[num], N), pre + 1)\r\n",
    "                cur = min(cur, f[table[num]])\r\n",
    "                num //= table[num]\r\n",
    "            pre = cur\r\n",
    "        return pre if pre != N else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
